#include <algorithm>
#include <iterator>
#include <sstream>
#include <iostream>
#include "sort.h"

inline void swap(int nums[], int pos1, int pos2)
{
    int tmp = nums[pos1];
    nums[pos1] = nums[pos2];
    nums[pos2] = tmp;
}

// In place quick sort an array
void quick_sort_array_in_place(int nums[], int left, int right
    , int pivot_index)
{
    if(right < left)
    {
        std::ostringstream oss;
        oss << "Error in calling quick_sort_array_in_place(nums, "
            << left << ", " << right << ", " << pivot_index << ")";
        throw oss.str();
    }
    if(right == left)
    {
        return;
    }

    if(-1 == pivot_index)
    {
        pivot_index = (right + left)/2;
    }

    int pivot = nums[pivot_index];

    swap(nums, pivot_index, right);

    pivot_index = left;
    for(int i = left; i < right; ++ i)
    {
        if(nums[i] <= pivot)
        {
            swap(nums, pivot_index, i);
            ++ pivot_index;
        }
    }
    swap(nums, pivot_index, right);
    if(pivot_index != left)
    {
        quick_sort_array_in_place(nums, left, pivot_index - 1);
    }
    if(pivot_index != right)
    {
        quick_sort_array_in_place(nums, pivot_index + 1, right);
    }
}

// Basic quick sort using vectors
void quick_sort_basic2(std::vector<int> & nums)
{
    if(nums.size() < 2)
    {
        return;
    }

    std::vector<int> smaller, larger;
    std::vector<int>::iterator it = nums.begin();

    int pivot = *it;
    ++ it;
    while (it != nums.end())
    {
        if ((*it) < pivot)
            smaller.push_back(*it);
        else
            larger.push_back(*it);
        ++ it;
    }

    quick_sort_basic2(smaller);
    quick_sort_basic2(larger);

    nums = smaller;
    nums.push_back(pivot);
    std::copy(larger.begin(), larger.end(), std::back_inserter(nums));
}

void quick_sort_in_place(std::vector<int> & nums)
{

}

